package formal.array;

/**
 * @author DengYuan2
 * @create 2021-02-04 21:45
 */
public class M_240 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
        int target = 17;
        boolean res = searchMatrix2(matrix, target);
        System.out.println(res);
    }

    /**
     * 额-我觉得可以，但是提交时显示：超出时间限制......
     *
     * @param matrix
     * @param target
     * @return
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        return helper(matrix, target, 0, 0);
    }

    public static boolean helper(int[][] matrix, int target, int r, int c) {
        boolean res = false;
        if (r < matrix.length && c < matrix[0].length) {
            if (matrix[r][c] == target) {
                return true;
            } else if (matrix[r][c] < target) {
                //先往右找
                res = helper(matrix, target, r, c + 1);
                //右边没有，再往下找
                if (!res) {
                    res = helper(matrix, target, r + 1, c);
                }
            }
        }
        return res;
    }

    /**
     * 大神的写法-关键是思路啊，从不同的点看问题！！！
     * 这里选择的是右上角，也可以选择左下角
     * @param matrix
     * @param target
     * @return
     */
    public static boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int r = 0, c = col - 1;
        while (r < row && c >= 0) {
            if (matrix[r][c] == target) {
                return true;
            } else if (matrix[r][c] > target) {
                c--;
            } else {
                r++;
            }
        }
        return false;
    }

}
